﻿\documentclass[twocolumn,10pt,a4paper]{article}

\def\myversion{2013-02-18}

\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{mathabx}
\usepackage[ngerman]{babel}
\usepackage[noheadfoot,top=1.5cm,bottom=2.5cm,left=1.5cm,right=1.5cm]{geometry}
\usepackage{fancyhdr}
\usepackage{wasysym} % \smiley :)
\usepackage{enumitem}
\usepackage{scalefnt}
\usepackage{sectsty} % section formatting
\usepackage{graphicx} % scalebox, rotatebox
\usepackage{multirow}
\usepackage{ifthen}
\usepackage{mathrsfs}
\usepackage{trsym} % Fourier-Transformation-Symbole
\usepackage{stmaryrd} % \varoast

%~ \linespread{1.1} % a bissl mehr platz zwischen den zeilen

\newcommand{\menge}{\mathbb} % menge in mengenschrift ^^
\newcommand{\R}{\menge{R}} % shortcut
\newcommand{\N}{\menge{N}} % shortcut
\newcommand{\Z}{\menge{Z}} % shortcut
\newcommand{\C}{\menge{C}} % shortcut
\newcommand{\Cov}[1]{\mathrm{Cov}\left[#1\right]}
\newcommand{\E}[1]{\mathrm{E}\left[#1\right]}
\newcommand{\Var}[1]{\mathrm{Var}\left[#1\right]}


% aufzählungs-liste mit kleinbuchstaben
% \begin{abc}
%     \item punkt a...
%     \item punkt b...
% \end{abc}
\newenvironment{abc}{\begin{enumerate}[label={\alph*)}]}{\end{enumerate}}
\newenvironment{iii}{\begin{enumerate}[label={\roman{*})}]}{\end{enumerate}}

%%%

% kleinere matrizen
% http://forum.mathematex.net/latex-f6/taille-matrice-t6799.html#p70671
\newenvironment{psmallmatrix}{\left(\begin{smallmatrix}}{\end{smallmatrix}\right)}
\renewenvironment{pmatrix}{\begin{psmallmatrix}}{\end{psmallmatrix}}
% standard ddots und vdots werden zu hoch in smallmatrix, ldots okay
% rotatebox funktioniert nicht bei dvi output!
\renewcommand{\ddots}{$\scalebox{1}[.5]{\rotatebox[origin=c]{135}{$\ldots$}}$}
\renewcommand{\vdots}{$\scalebox{1}[.5]{\rotatebox[origin=c]{90}{$\ldots$}}$}


\makeatletter
\def\ownrbrace#1{{\hbox{$\left\rbrace\vbox to#1\p@{}\right.\n@space$}}} 
\def\ownlbrace#1{{\hbox{$\left.\vbox to#1\p@{}\right\lbrace\n@space$}}} 
\makeatother

\setlist{itemsep=.01mm} % abstand zwischen \item verkleinern
\setlength{\columnsep}{1cm} % twocolumn abstand
\parindent 0mm % AbSatzeinzug auf 0 setzen
\pagestyle{fancy}
\lhead{} % aktuelle überschrift ausblenden
\rhead{} % seitenzahl ausblenden -- erst nach TOC anzeigen
\cfoot{} % seitenzahl ausblenden
\renewcommand{\headrulewidth}{0mm} % header trennlinie ausblenden
% überschriften anpassen: klein, nicht fett, unterstrich
%\allsectionsfont{\small \rm \sectionrule{0pt}{0pt}{-1.2pt}{0.2pt}}
%\partfont{\Large \sc} % Parts groß und in Kapitälchen
\partfont{\large \rm \sectionrule{0pt}{0pt}{-1.8pt}{0.5pt}}
\sectionfont{\small \rm \sectionrule{0pt}{0pt}{-1.2pt}{0.25pt}}
\subsectionfont{\small \rm \sectionrule{0pt}{0pt}{-1.2pt}{0.25pt}}
\subsubsectionfont{\small \rm}
\makeatletter
% tex/latex/base/article.cls
\renewcommand\thepart{\@arabic\c@part}
\renewcommand\thesection{\@arabic\c@part.\@arabic\c@section}
\makeatother
\renewcommand\part[1]{\refstepcounter{part}\section*{\thepart\hspace{1em}#1}\setcounter{section}{0}}

% \re und \im nicht in frakturschrift
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}

\renewcommand{\bar}{\overline} % \bar breiter
\renewcommand{\tilde}{\widetilde} % \tilde breiter
\renewcommand{\hat}{\widehat} % \hat breiter


% mehr platz vor und nach \forall
\let\origforall\forall
\renewcommand{\forall}{\textrm{ }\origforall\textrm{ }}

% mehr platz nach \exists
\let\origexists\exists
%\edef\exists{\exists\textrm{ }}
\renewcommand{\exists}{\origexists\textrm{ }}
\renewcommand{\vec}{\mathbf}
\newcommand{\vecg}{\boldsymbol}
\newcommand{\mat}{\mathbf}
\newcommand{\matg}{\boldsymbol}

\newcommand{\conv}{\convolution\hspace{-1mm}\convolution\hspace{0.5mm}}

\begin{document}
\scalefont{0.8} % schriftgröße skalieren: 10pt --> 8pt

\begin{center}
  {\Large Multidimensional Digital}\\
  {\Large Signal Processing}\\
  {\small Or plain: Image processing for dummies.}\\
  {Version \myversion}
\end{center}

\part{MD signals and systems}
\section{Periodic sequences}
Let $\vec n,\vec r \in \N^k$ and $\mat N,\mat P \in \N^{k\times k}$.
$x(\vec n)$ is peridioc if
\begin{equation}
    x(\vec n + \mat N\vec r) = x(\vec n).
\end{equation}
The number of samples in one period is
\begin{equation}
    |\det(\mat N)|,
\end{equation}
and $\mat N\mat P$ is also a valid periodicity matrix.

\section{Linear shift-invariant systems}
Let $a,b \in \C$ and let $v(\vec n) = au_1(\vec n) + bu_2(\vec n)$
and $w(\vec n) = u(\vec n-\vec m)$.
A system $\mathcal L$ is linear and shift-invariant (LSI) if
\begin{enumerate}
    \item $\mathcal L[v](\vec n) = a\mathcal L[u_1](\vec n)+b\mathcal L[u_2](\vec n),$ 
    \item $\mathcal L[w](\vec n) = \mathcal L[u](\vec n - \vec m).$
\end{enumerate}
If $\mathcal L$ is linear and $y(n_1,n_2) := L[x](n_1,n_2)$ then
\begin{equation}
    y(n_1,n_2) = \sum\limits_{k_1=-\infty}^{\infty}\sum\limits_{k_2=-\infty}^{\infty}
    x(k_1,k_2)\underbrace{\mathcal L[\delta](n_1-k_1,n_2-k_2)}_{h_{k_1k_2}(n_1,n_2)}.
\end{equation}
If $\mathcal L$ is also shift-invariant then
\begin{equation}
        h := h_{00}(n_1-k_1,n_2-k_2) = h_{k_1k_2}(n_1,n_2).
\end{equation}

\section{2D convolution}
\begin{enumerate}
    \item $x \conv h = \sum\limits_{k_1=-\infty}^{\infty}\sum\limits_{k_2=-\infty}^{\infty}
    x(k_1,k_2)h(n_1-k_1,n_2-k_2)$
    \item $x \conv h = h \conv x$
    \item $(x \conv h) \conv g = x \conv (h\conv g)$
    \item $x \conv (h+g) = (x\conv h) + (x\conv g)$
\end{enumerate}
\section{Separable systems}
If $h(n_1,n_2) = h_1(n_1)h_2(n_2)$ then
\begin{equation}
    y(n_1,n_2) = h_1 \convolution(h_2\convolution x).
\end{equation}
That is
\begin{enumerate}
    \item $g(n_1,n_2) = h_2\convolution x = \sum\limits_{k_2=-\infty}^\infty
           h_2(k_2)x(n_1,n_2-k_2)$,
    \item $y(n_1,n_2) = h_1\convolution g = \sum\limits_{k_1=-\infty}^\infty
           h_1(k_1)g(n_1-k_1,n_2)$.
\end{enumerate}

\section{BIBO stability}
A system is BIBO stable if
\begin{equation}
    \sum\limits_{k_1=-\infty}^{\infty}\sum\limits_{k_2=-\infty}^{\infty}
    |h(n_1,n_2)| = S_1 < \infty
\end{equation}

\section{Fourier transform}
The Fourier transform is defined as
\begin{equation}
    X(\omega_1,\omega_2) = \sum\limits_{n_1}\sum\limits_{n_2}x(n_1,n_2)
        \exp(-j\omega_1n_1-j\omega_2n_2).
\end{equation}
$X$ is periodic with $\mat N = \begin{bmatrix}
        2\pi & 0 \\ 0 & 2\pi
    \end{bmatrix}$. Its inverse transform is
\begin{equation}
x(n_1,n_2) = \frac{1}{4\pi^2}\int\limits_{-\pi}^{\pi}\int\limits_{-\pi}^{\pi}
X(\omega_1,\omega_2)\exp(j\omega_1n_1+j\omega_2n_2)d\omega_1d\omega_2.
\end{equation}
Some nice properties:
\begin{enumerate}
    \item $a,b\in\C : ax_1+by_1 \TransformHoriz aX_1+bX_2$
    \item $x(n_1-k_1,n_2-k_2) \TransformHoriz \exp(-j\omega_1k_1-j\omega_2k_2)X(\omega_1,\omega_2)$
    \item $\exp(j\theta_1n_1+j\theta_2n_2)x(n_1,n_2) \TransformHoriz X(\omega_1-\theta_1,\omega_2-\theta_2)$
    \item $h \conv x \TransformHoriz HX$
\end{enumerate}

\part{Discrete fourier transform}
\section{Discrete fourier series}
Let $x$ be periodic with with $\mat N = \begin{bmatrix}
        N_1 & 0 \\ 0 & N_2
    \end{bmatrix}$.
Them its 2D fourier series is
\begin{equation}
    x(n_1,n_2) = \frac{1}{N_1N_2}\sum\limits_{k_1=0}^{N_1-1}\sum\limits_{k_2=0}^{N_2-1}
    X(k_1,k_2)\exp(j \frac{2\pi}{N_1}n_1k_1+j\frac{2\pi}{N_2}n_2k_2),
\end{equation}
with
\begin{equation}
    X(k_1,k_2) = \sum\limits_{n_1=0}^{N_1-1}\sum\limits_{n_2=0}^{N_2-1}
    x(n_1,n_2)\exp(-j\frac{2\pi}{N_1}n_1k_1-j\frac{2\pi}{N_2}n_2k_2).
\end{equation}
It also holds that
\begin{equation}
    X(k_1,k_2) = \left.X(\omega_1,\omega_2)\right|_{\omega_1=2\pi \frac{k_1}{N_1},\omega_2=2\pi \frac{k_2}{N_2}}
\end{equation}
if $X(\omega_1,\omega_2)$ is the FT of one period of $x$.

\part{Linear block transforms}
\section{Separable unitary block transforms}
The forward transform is
\begin{equation}
\mat Y = \mat A\mat X\mat A^T
\end{equation}
and the backward transform is
\begin{equation}
\mat X = \mat A^H\mat Y\mat A^*
\end{equation}
Let $\mat A = (\vec a_1,\dots,\vec a_N)$. Then, $\mat X$ can be written as a linear combination of basis images.
\begin{equation}
    \mat X = \sum\limits_{k=1}^{N}\sum\limits_{l=1}^{N}y_{kl}\vec a_k\vec a_l^T
\end{equation}

\section{Separable block transforms}
The forward transform is
\begin{equation}
\mat Y = \mat A_1\mat X\mat A_2^T.
\end{equation}
It can be also written as
\begin{equation}
\vec y = \mat A_{2D}\vec x
\end{equation}
if is $\vec x$ is extraced row-wise from $\mat X$ and
\begin{equation}
    \mat A_{2D} = \mat A_1 \otimes \mat A_2 = \begin{bmatrix}
        (\mat A_1)_{11}\mat A_2 & \dots & (\mat A_1)_{1N}\mat A_2 \\
        \vdots & \ddots & \vdots \\
        (\mat A_1)_{N1}\mat A_2 & \dots & (\mat A_1)_{NN}\mat A_2 \\
    \end{bmatrix}.
\end{equation}

\section{Haar transform}
\begin{equation}
\mat H_2 = \begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix}
\end{equation}
\begin{equation}
\mat H_{2^{k+1}} = \begin{bmatrix}
\mat H_{2^k} \otimes \begin{bmatrix}1 & 1\end{bmatrix} \\
2^{\frac{k}{2}}\mat I_{2^k} \otimes \begin{bmatrix}1 & -1\end{bmatrix} \\
\end{bmatrix}
\end{equation}
\begin{equation}
\mat A_{2^k}^{Haar} = \frac{1}{\sqrt{2^k}}H_{2^k}
\end{equation}

\section{Hadamard transform}
\begin{equation}
\mat A_{2}^{Had} = \frac{1}{\sqrt{2}}\begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix}
\end{equation}
\begin{equation}
\mat A_{2^k}^{Had} = \bigotimes\limits_{l=1}^{k}\mat A_{2}^{Had}
\end{equation}

\section{Unitary DFT}
\begin{equation}
\mat A_M^{DFT} = \frac{1}{\sqrt{M}}\begin{bmatrix}
1 & 1 & 1 & \dots & 1 \\
1 & e^{-j \frac{2\pi}{M}} & e^{-j \frac{4\pi}{M}} & \dots & e^{-j \frac{2\pi(M-1)}{M}} \\
1 & e^{-j \frac{4\pi}{M}} & e^{-j \frac{8\pi}{M}} & \dots & e^{-j \frac{4\pi(M-1)}{M}} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & e^{-j \frac{2\pi(M-1)}{M}} & e^{-j \frac{4\pi(M-1)}{M}} & \dots & e^{-j \frac{2\pi(M-1)^2}{M}} \\
\end{bmatrix}
\end{equation}

\section{Unitary DCT}
\begin{equation}
(\mat A_M^{DCT})_{kn} = \left\{\begin{matrix}
    \frac{1}{\sqrt{M}} & k=0\\
    \sqrt{\frac{2}{M}}\cos\frac{\pi(2n+1)k}{2M} & k \neq 0\\
\end{matrix}\right.
\end{equation}
\begin{equation}
\mat A_M^{DCT} = \sqrt{\frac{2}{M}}\begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & \dots & \frac{1}{\sqrt{2}} \\
\cos\frac{\pi}{2M} & \cos\frac{3\pi}{2M} & \dots & \cos\frac{(2M-1)\pi}{2M} \\
\cos\frac{2\pi}{2M} & \cos\frac{6\pi}{2M} & \dots & \cos\frac{2(2M-1)\pi}{2M} \\
\vdots & \vdots & \ddots & \vdots \\
\cos\frac{(M-1)\pi}{2M} & \cos\frac{(M-1)3\pi}{2M} & \dots & \cos\frac{(M-1)(2M-1)\pi}{2M} \\
\end{bmatrix}
\end{equation}

\section{KLT}
Let $\mat U\mat\Lambda\mat U^H$ be the eigendecomposition of the
covariance matrix $\E{\vec X\vec X^T}-\vecg\mu\vecg\mu^T$ or the autocorrelation
matrix $\E{\vec X\vec X^T}$. Then the KLT is defined as
\begin{equation}
    \mat A^{KLT} = \mat U^H\vec x.
\end{equation}
The KLT minimises the energy packing coefficient
\begin{equation}
\eta_e(m) = \frac{\sum\limits_{k=0}^{m-1} \E{y_k^2}}{\E{\vec y^T\vec y}}.
\end{equation}
The decorrelation efficiency $\eta_c$ is 1 for the KLT, with
\begin{equation}
\eta_c = 1 - \frac{\sum\limits_{k=0}^{M-1}\sum\limits_{l=0,k\neq l}^{M-1} |r_{yy}(k,l)|}
{\sum\limits_{k=0}^{M-1}\sum\limits_{l=0,k\neq l}^{M-1} |r_{xx}(k,l)|}.
\end{equation}

\part{Multiresolution theory}
\section{Resolution pyramids}
The total number of pixels of a $M\times N$ signal in a $P+1$ level pyramid is
\begin{equation}
MN\left(1+\frac{1}{4}+\frac{1}{4^2}+\dots+\frac{1}{4^P}\right) \leq \frac{4}{3}MN.
\end{equation}
\section{Critically sampled filterbank}
A filterbank is called critically samples if the amount of samples stays
the same before analysis and after synthesis. That is, suppose you have
$M$ subsamplers with a subsampling ratio of $1 : k_i$. Then it should hold
that
\begin{equation}
\frac{1}{k_0} + \frac{1}{k_1} + \dots + \ \frac{1}{k_{M-1}} = 1
\end{equation}

\section{Effect of up-/downsampling}
\subsection{Continuous fourier transform}
If we decimate $X(\omega)$ by the the factor $m$, then
\begin{equation}
Y(\omega) = \frac{1}{m} \sum\limits_{l=0}^{m-1} X\left(\frac{\omega}{m} + 2\pi\frac{l}{m}\right).
\end{equation}
\subsection{Z-transform}
\subsubsection{Upsampling}
Upsampling $x(n)$ by the factor $L$ yields
\begin{equation}
    y(n) = \left\{\begin{matrix}
    x\left(\frac{n}{L}\right) & : & n\bmod{L}=0 \\
    0 & : & \mathrm{else} \\
\end{matrix}\right..
\end{equation}
The z-transform of $y(n)$ is
\begin{equation}
    Y(z) = \sum\limits_{k=-\infty}^\infty y(k)z^{-k}
\end{equation}
As $y(n)$ is only nonzero for $k=Ln$ it holds that
\begin{equation}
    Y(z) = \sum\limits_{n=-\infty}^\infty y(Ln)z^{-Ln}=
    \sum\limits_{n=-\infty}^\infty x(n)(z^L)^{-n} = X(z^L).
\end{equation}
\subsubsection{Downsampling}
Let
\begin{equation}
    q_L(k) = \left\{\begin{matrix}
    1 & : & k\bmod{L} = 0\\
    0 & : & \mathrm{else}\\
    \end{matrix}\right..
\end{equation}
Let $y(k)=x(Lk)$ and let $l=\frac{n}{L}$. Then
\begin{equation}
    Y(z) = \sum\limits_{l=-\infty}^\infty x(Ll)z^{-l} =
    \sum\limits_{n=-\infty}^\infty x(n)q_L(n)z^{-\frac{n}{L}}.
\end{equation}
For $L=2$ one can write $q_2(k)$ as
\begin{equation}
    q_2(k) = \frac{1}{2}((-1)^{-k}+1).
\end{equation}
Thus
\begin{equation}
\begin{array}{rcl}
Y(z) &=& \sum\limits_{n=-\infty}^\infty x(n)q_2(n)z^{-\frac{n}{2}} \\
     &=& \sum\limits_{n=-\infty}^\infty x(n)\frac{1}{2}((-1)^{-n}+1)z^{-\frac{n}{2}} \\
     &=& \frac{1}{2}\left(\sum\limits_{n=-\infty}^\infty (-1)^{-n}x(n)z^{-\frac{n}{2}}
         + \sum\limits_{n=-\infty}^\infty x(n)z^{-\frac{n}{2}}\right)\\
     &=& \frac{1}{2}\left(\sum\limits_{n=-\infty}^\infty x(n)(-z^{\frac{1}{2}})^{-n}
         + \sum\limits_{n=-\infty}^\infty x(n)z^{-\frac{n}{2}}\right)\\
     &=& \frac{1}{2}\left(X(-\sqrt{z}) + X(\sqrt{z})\right).
\end{array}
\end{equation}
So in short decimation by 2 is
\begin{equation}
Y(z) = \frac{1}{2}\left(X(-\sqrt{z}) + X(\sqrt{z})\right).
\end{equation}

\section{Frequency response of a 2-channel filterbank}
Let $F_0, F_1$ denote the analysis filters and $G_0, G_1$ the synthesis
filters. Then
\begin{equation}
\begin{array}{rcl}
\hat X(\omega) &=& \frac{1}{2}\left(F_0(\omega)G_0(\omega)+F_1(\omega)G_1(\omega)\right)X(\omega)\\
&+& \frac{1}{2}\left(F_0(\omega+\pi)G_0(\omega)+F_1(\omega+\pi)G_1(\omega)\right)X(\omega+\pi).
\end{array}
\end{equation}

We get aliasing cancellation if
\begin{equation}
\begin{array}{rcl}
    G_0(\omega)&=&F_1(\omega+\pi),\\
    -G_1(\omega)&=&F_0(\omega+\pi)\\
    &\mathrm{or}&\\
    -G_0(\omega)&=&F_1(\omega+\pi),\\
    G_1(\omega)&=&F_0(\omega+\pi)\\
    &\mathrm{or}&\\
    g_0(n) &=& (-1)^nf_1(n),\\
    g_1(n) &=& (-1)^{n+1}f_0(n)\\
    &\mathrm{or}&\\
    g_0(n) &=& (-1)^{n+1}f_1(n),\\
    g_1(n) &=& (-1)^{n}f_0(n).
\end{array}
\end{equation}

\section{Design of a 2-channel perfect reconstruction filter bank}
Let $z^{-l}$ be a delay by $l$. A filter bank with PR and aliasing cancellation
has to satisfy
\begin{equation}
F_0(z)G_0(z)+F_1(z)G_1(z)=2z^{-l}
\label{PRdelaycond}
\end{equation}
\begin{equation}
F_0(-z)G_0(z)+F_1(-z)G_1(z)= 0
\label{PRaliascond}
\end{equation}
To satisfy \eqref{PRaliascond} let
\begin{equation}
\begin{array}{rcl}
G_0(z) &=& F_1(-z) \\
G_1(z) &=& -F_0(-z).
\end{array}
\label{PRaliassat}
\end{equation}
Let $P_0(z) = G_0(z)F_0(z)$ and $P_1(z) = G_1(z)F_1(z)$. With\\
$P_1(z) = -P_0(z)$, \eqref{PRdelaycond} is satisifed if
\begin{equation}
    P_0(z)-P_0(-z) = 2z^{-l}.
    \label{PRcond}
\end{equation}
Thus there must be only one odd power $l$ in $P_0(z)$. The design of a
2-channel PR filter bank consists of two steps:
\begin{enumerate}
    \item Design a low-pass filter $P_0(z)$ satisfying \eqref{PRcond}.
    \item Factor $P_0(z)$ into $F_0(z)G_0(z)$ and get $F_1(z),G_1(z)$
    with \eqref{PRaliassat}.
\end{enumerate}

\part{The lifting implementation of the DWT}
\section{Polyphase representation}
Lifting is super duper. To do this we split the calculation of the even
and the odd samples for each channel of our filterbank.
\begin{equation}
    Y_e(z) = H_e(z)X_e(z) + z^{-1}H_0(z)X_0(z)
\end{equation}
$Y_e(z)$ includes subsampling implicitly. The polyphase representation
of a filter $H$ is
\begin{equation}
H(z) = H_e(z^2) + z^{-1}H_o(z^2)
\label{Hsplit}
\end{equation}
We can determine
$H_e(z)$ and $H_o(z)$ with
\begin{equation}
H_e(z^2) = \frac{H(z)+H(-z)}{2}
\end{equation}
and
\begin{equation}
H_o(z^2) = \frac{H(z)-H(-z)}{2z^{-1}}.
\end{equation}
Or you just take the even coefficients and throw them in $H_e(z^2)$ and throw
the odd ones in $H_o(z^2)$ (don't forget to divide the latter by $z^{-1}$).
Now we can represent our
filterbank with the polyphase matrix:
\begin{equation}
\begin{pmatrix}
    X_L(z) \\ X_H(z) \\
\end{pmatrix} =
\tilde{\boldsymbol{P}}(z)
\begin{pmatrix}
    X_e(z) \\ z^{-1}X_o(z) \\
\end{pmatrix}
\end{equation}
with
\begin{equation}
\tilde{\boldsymbol{P}}(z) = 
\begin{pmatrix}
    F_{0e}(z) & F_{0o}(z) \\
    F_{1e}(z) & F_{1o}(z) \\
\end{pmatrix}.
\end{equation}
$X_L(z)$ and $X_H(z)$ hereby denote the outputs of the analysis step. Note
that as $X_e(z)$ and $X_o(z)$ are subsampled versions of $X(z)$ you also have to
subsample the filters. That is, take $F_{0e}(z)$ instead of $F_{0e}(z^2)$
for example.

The synthesis matrix is
\begin{equation}
\boldsymbol{P}(z) = 
\begin{pmatrix}
    G_{0e}(z) & G_{1e}(z) \\
    G_{0o}(z) & G_{1o}(z) \\
\end{pmatrix}.
\end{equation}
Perfect reconstruction can be achieved if
\begin{equation}
\tilde{\boldsymbol{P}}(z^{-1})\boldsymbol{P}(z) = \mat I.
\end{equation}
That leads for example to 
\begin{equation}
\begin{array}{rcl}
    F_{0e}(z) &=& G_{1o}(z^{-1}), \\
    F_{0o}(z) &=& -G_{1e}(z^{-1}), \\
    F_{1e}(z) &=& -G_{0o}(z^{-1}), \\
    F_{1o}(z) &=& G_{0e}(z^{-1}).
\end{array}
\end{equation}
With \eqref{Hsplit} it also holds
\begin{equation}
\begin{array}{rcl}
    F_{0}(z) &=& -z^{-1}G_{1}(z^{-1}), \\
    F_{1}(z) &=& z^{-1}G_{0}(-z^{-1}).
\end{array}
\end{equation}
If $F_0=G_0$ and $F_1=G_1$ the wavelet transform is orthogonal otherwise
it is biorthogonal. If $\det(\boldsymbol P(z))=1$ then the filter pair
$(G_0,G_1)$ is called complementary. If $(G_0,G_1)$ is complementary, so
is $(F_0,F_1)$.

\section{Laurent polynomials/series}
A Laurent series is
\begin{equation}
    h(z) = \sum\limits_{k=p}^q h_k z^{-k}.
\end{equation}
The degree of a LP is
\begin{equation}
|h| = q-p.
\end{equation}
For two LPs $a(z)$ and $b(z)$ with $|a(z)|>|b(z)|$ there always exists a
$q(z)$ with $|q(z)|=|a(z)|-|b(z)|$ and $r(z)$ with $|r(z)|<|b(z)|$ such that
\begin{equation}
a(z)=b(z)q(z)+r(z)
\end{equation}

\section{The euclidean algorithm}
Let $|a(z)|\geq|b(z)|$, $b(z) \neq 0$, $a_0(z)=a(z)$ and $b_0(z)=b(z)$.
Then
\begin{equation}
\begin{array}{rcl}
    a_{i+1}(z) &=& b_i(z)\\
    b_{i+1}(z) &=& a_i(z)\bmod{b_i(z)}
\end{array}
\end{equation}
There exists some $n$ with $b_n(z)=0$. Then $a_n(z)=\gcd(a(z),b(z))$.
With $q_{i+1}(z) = \frac{a_i(z)}{b_i(z)}$ (without remainder) it holds that
\begin{equation}
a_i(z) = q_{i+1}(z)b_i(z)+b_{i+1}(z).
\end{equation}
Rewriting that in a matrix yields
\begin{equation}
\begin{pmatrix}
a_i(z) \\ b_i(z)
\end{pmatrix} =
\begin{pmatrix}
q_{i+1}(z) & 1 \\
1 & 0 \\
\end{pmatrix} 
\begin{pmatrix}
a_{i+1}(z) \\ b_{i+1}(z)
\end{pmatrix}.
\end{equation}
Thus
\begin{equation}
\begin{pmatrix}
a(z) \\ b(z)
\end{pmatrix} = 
\prod\limits_{i=1}^{n}
\begin{pmatrix}
q_i(z) & 1 \\
1 & 0 \\
\end{pmatrix} 
\begin{pmatrix}
a_{n}(z) \\ 0
\end{pmatrix}.
\end{equation}

\section{Lifting theorem}
If $(G_0,G_1)$ is complementary, so is $(G_1',G_0)$ only if
\begin{equation}
G_1'(z) = G_1(z) + G_0(z)s(z^2).
\label{lifttheorem}
\end{equation}
Similar statements hold for $G_0', F_0'$ and $F_1'$:
\begin{equation}
G_0'(z) = G_0(z) + G_1(z)t(z^2),
\end{equation}
\begin{equation}
F_0'(z) = F_0(z) - F_1(z)s(z^{-2}),
\end{equation}
\begin{equation}
F_1'(z) = F_1(z) - F_0(z)t(z^{-2}).
\end{equation}

\section{From the lifting theorem to lifting steps}
Consider again \eqref{lifttheorem}. Using \eqref{Hsplit} $G_{1e}'$ and $G_{1o}'$ are
\begin{equation}
\begin{array}{c}
    G_{1e}' = G_{1e}(z) + G_{0e}(z)s(z)\\
    G_{1o}' = G_{1o}(z) + G_{0o}(z)s(z)\\
\end{array}.
\end{equation}
Rewriting this in a matrix together with $G_{0e}$ and $G_{0o}$ yields
\begin{equation}
\begin{pmatrix}
G_{0e}(z) & G_{1e}'(z) \\
G_{0o}(z) & G_{1o}'(z)
\end{pmatrix} = 
\begin{pmatrix}
    G_{0e}(z) & G_{1e}(z) \\
    G_{0o}(z) & G_{1o}(z) \\
\end{pmatrix}
\begin{pmatrix}
1 & s(z)\\
0 & 1
\end{pmatrix}.
\end{equation}
One can identify the polyphase matrix and rewrite this to
\begin{equation}
\boldsymbol{P}'(z) = \boldsymbol{P}(z)\begin{pmatrix}
1 & s(z)\\
0 & 1
\end{pmatrix}.
\end{equation}
Similarly holds
\begin{equation}
G_0' : \boldsymbol{P}'(z) = \boldsymbol{P}(z)\begin{pmatrix}
1 & 0\\
t(z) & 1
\end{pmatrix},
\end{equation}
\begin{equation}
F_0' : \tilde{\boldsymbol{P}}'(z) = \begin{pmatrix}
1 & -s(z^{-1})\\
0 & 1
\end{pmatrix}\tilde{\boldsymbol{P}}(z),
\end{equation}
\begin{equation}
F_1' : \tilde{\boldsymbol{P}}'(z) = \begin{pmatrix}
1 & 0\\
-t(z^{-1}) & 1
\end{pmatrix}\tilde{\boldsymbol{P}}(z).
\end{equation}
We call
\begin{equation}
\boldsymbol{\mathcal U} = \begin{pmatrix}
1 & s(z)\\
0 & 1
\end{pmatrix}
\end{equation}
an update matrix,
\begin{equation}
\boldsymbol{\mathcal P}  = \begin{pmatrix}
1 & 0\\
t(z) & 1
\end{pmatrix}
\end{equation}
a prediction matrix and
\begin{equation}
\boldsymbol{\mathcal{L}}  = \begin{pmatrix}
a & 0\\
0 & b
\end{pmatrix}
\end{equation}
a lazy wavelet transform. We can factorize $\boldsymbol{P}$ as
\begin{equation}
\boldsymbol{P} = \boldsymbol{\mathcal{L}}\dots
{\boldsymbol{\mathcal{U}}}_2
\boldsymbol{\mathcal{P}}_2
\boldsymbol{\mathcal{U}}_1
\boldsymbol{\mathcal{P}}_1
\end{equation}
and $\tilde{\boldsymbol{P}}$ as
\begin{equation}
\tilde{\boldsymbol{P}} = \dots
{\boldsymbol{\mathcal{U}}}_2
\boldsymbol{\mathcal{P}}_2
\boldsymbol{\mathcal{U}}_1
\boldsymbol{\mathcal{P}}_1
\boldsymbol{\mathcal{L}}.
\end{equation}

\part{Geometric wavelets}
\section{Radon transform}
The radon transform is
\begin{equation}
    r(\rho,\theta) = \int\limits_{-\infty}^\infty\int\limits_{-\infty}^\infty
    f(x,y)\delta(x\cos(\theta)+y\sin(\theta)-\rho)dxdy
\end{equation}
with $\rho \in (-\infty,\infty), \theta \in [0,2\pi)$. Its is symmetric with
\begin{equation}
\begin{array}{rcl}
    r(\rho,\theta+\pi) &=& r(-\rho,\theta),\\
    r(-\rho,\theta+\pi) &=& r(\rho,\theta).
\end{array}
\end{equation}
The fourier transform for a fixed $\theta$ is
\begin{equation}
    R_\theta(\omega) = \int\limits_{-\infty}^\infty r(\rho,\theta)e^{-j2\pi\omega\rho}d\rho.
\end{equation}
Inserting the definition of the radon transform yields
\begin{equation}
R_\theta(\omega) = \int\limits_{-\infty}^\infty\int\limits_{-\infty}^\infty
f(x,y)e^{-j2\pi\omega(x\cos(\theta)+y\sin(\theta))}dxdy.
\end{equation}
By substituting $u=\omega\cos(\theta)$ and $v=\omega\sin(\theta)$ it holds that
\begin{equation}
    R_\theta(\omega) = F(\omega\cos(\theta),\omega\sin(\theta)).
\end{equation}
If we do some stuff we end up with
\begin{equation}
f(x,y) = \int\limits_0^\pi\left[\int\limits_{-\infty}^\infty
|\omega|R_\theta(\omega)e^{j2\pi\omega\rho}d\omega\right]_{\rho=x\cos(\theta)+y\sin(\theta)}
d\theta.
\end{equation}
As is this is not integrable it needs to be multiplied with a window function,
e.g.
\begin{equation}
h(\omega)=\left\{
\begin{matrix}
    1 & : & |\omega| \in [0,\omega_{max}] \\
    0 & : & \mathrm{else}
\end{matrix}\right.
\end{equation}
or
\begin{equation}
h(\omega)=\left\{
\begin{matrix}
    c + (c-1)\cos(\frac{2\pi\omega}{M-1}) & : & \omega \in [0,M) \\
    0 & : & \mathrm{else}
\end{matrix}\right..
\end{equation}
The latter is called Hamming window for $c=0.54$ or Hann window for $c=0.5$.
So to summarise the inverse radon transform consists of these steps:
\begin{enumerate}
    \item Calculate $R_\theta(\omega)$.
    \item Multiply $R_\theta(\omega)$ by $h(\omega)|\omega|$.
    \item Calculate the inverses of $h(\omega)|\omega|R_\theta(\omega)$
    for each $\theta$.
    \item Sum all the inverses.
\end{enumerate}

\section{Discrete radon transform}
The discrete radon transform is
\begin{equation}
r(\rho,\theta) = \sum\limits_{x=0}^{M-1}\sum\limits_{y=0}^{N-1}
f(x,y)\delta(x\cos(\theta)+y\sin(\theta)-\rho)
\end{equation}










\end{document}
